package SegmentTree;

/**
 * 线段树范围为1 ~ n 时，需要几倍空间才够用
 */
public class HowManySpace {
    /**
     * @param l 左边界
     * @param r 右边界
     * @param i 这个范围的信息存储在i位置
     * @return 最大编号
     */
    public static int maxi(int l, int r, int i) {
        if (l == r) {
            return i;
        } else {
            int mid = (l + r) / 2;
            // i << 1 | 1 == i * 2 + 1
            return Math.max(maxi(l, mid, i << 1), maxi(mid + 1, r, i << 1 | 1));
        }
    }

    public static void main(String[] args) {
        int n = 100;
        int a = 0, b = 0;
        double t = 0;
        for (int i = 1; i <= n; i++) {
            int space = maxi(1, i, 1);
            double times = (double) space / (double) i;
            System.out.println("范围[1~" + i + "]," + "需要空间" + space + ",倍速=" + times);
            if (times > t) {
                a = i;
                b = space;
                t = times;
            }
        }

        System.out.println("其中的最大倍速，范围[1~" + a + "]," + "需要空间" + b + ",倍速=" + t);
    }
}
